package Offer.offer2022;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

import domain.TreeNode;

/**
 * @author: leiwenkang
 * @date: 2020/6/7
 * @time: 17:35
 */
public class 之字形打印二叉树 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        Zprint(root);
    }

    public static ArrayList<ArrayList<Integer>> Zprint(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            LinkedList<Integer> layerList = new LinkedList<>();
            for (int i = 0; i < queue.size(); i++) {
                TreeNode temp = queue.poll();
                if ((result.size() & 1) == 0) {
                    layerList.addLast(temp.val);
                } else {
                    layerList.addFirst(temp.val);
                }

                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }
            result.add(new ArrayList<>(layerList));
        }
        return result;

    }
}
